π§· νΈλΌμ΄
ν¨μ¨μ μΈ λ¬Έμμ΄ μ μ₯ λ° νμμ΄ κ°λ₯ν μλ£κ΅¬μ‘°μ΄λ€.
μλλ
Triλ‘ λΆλ Έμλ€. νμ§λ§ λ§λ‘ ν λTreeμ ꡬλΆλμ§ μλ κ²½ν₯μ΄ μμ΄Trie(νΈλΌμ΄)λ‘ λΆλ¦¬κΈ° μμνλ€.
μ λ§μ λ¬Έμμ΄μ μ μ₯νμλλ° μ λ ₯μΌλ‘ μ΄λ€ λ¬Έμμ΄μ΄ μ£Όμ΄μ‘μ λ, λ΄κ° μ μ₯ν λ¬Έμμ΄μ ν¬ν¨λ λ¬Έμμ΄μΈμ§ μ μ μλ λ°©λ²μ μλμ κ°μ λ°©μλ€μ΄ μμ κ²μ΄λ€.
-
λ¨μ λΉκ΅
- λ¨μνκ² μ 체 λ¬Έμμ΄μ μ²μλΆν° λκΉμ§ κ°λ³ λ¬Έμλ₯Ό λΉκ΅νλ λ°©μ
- μ΅λ λ¬Έμμ΄ κΈΈμ΄
m, μ 체 λ¬Έμ κ°μnκ°μΌ κ²½μ°, μκ°λ³΅μ‘λ:
-
μ΄μ§ νμ κΈ°λ²
- μ 체 λ¬Έμμ΄μ μ¬μ μμΌλ‘ λ°°μ΄ μ μ₯ ν, μ€κ° κ°κ³Ό λΉκ΅ν΄ μ¬μ μ μΌλ‘ μ΄μ μ΄λ©΄ μ’μΈ‘μ λ° / μ΄νλ©΄ μ°μΈ‘μ λ°μΌλ‘ λΉκ΅ λ°λ³΅ λ°©μ
- μ΅λ λ¬Έμμ΄ κΈΈμ΄
m, μ 체 λ¬Έμ κ°μnκ°μΌ κ²½μ°, μκ°λ³΅μ‘λ: μ λ ¬: / νμ: μ¦,
-
νΈλΌμ΄(
Trie)- K-μ§ νΈλ¦¬ ꡬ쑰λ₯Ό ν΅ν΄ λ¬Έμμ΄μ μ μ₯νλ λ°©μ
gameμ΄λΌλ λ¨μ΄λ₯Ό μ°Ύλλ€λ©΄,gλ₯Ό μ°Ύκ³ μμλλ‘a,m,eλ₯Ό μ°Ύλλ°, μ΄λ₯Ό νΈλ¦¬νμμΌλ‘ ꡬνν κ²- 맨 μμ μ λμ΄(prefix)λΆν° μμνμ¬ λ¨μ΄ μ 체λ₯Ό μ°Ύμκ°λ κ³Όμ μ΄λ―λ‘ μ λμ¬ νΈλ¦¬(Prefix-Tree)λΌκ³ λ νλ€.
- λ¬Έμμ΄ μ μ₯μ μν 곡κ°μ λ§μ΄ μ°μ§λ§ νμμ λ§€μ° ν¨μ¨μ μ΄λΌλ νΉμ±μ κ°λλ€.
-
μ΅λ λ¬Έμμ΄ κΈΈμ΄
mμΌ λ λ¬Έμμ κ°μμ 무κ΄νκ² μκ°λ³΅μ‘λ:- λ¬Έμμ΄ κΈΈμ΄κ° λ무 컀μ
Mapλ±μ μ΄μ©ν΄ λμ ν λΉμ ν΄μΌ νλ κ²½μ° λ§νΌ μμν μ μλ€.
- λ¬Έμμ΄ κΈΈμ΄κ° λ무 컀μ
{"bar", "bag", "bark", "dog", "do", "door"}
πͺ μ₯λ¨μ
νΈλΌμ΄λ ν΄μ ν μ΄λΈμ λ체νλ λ° μ¬μ©λ μ μλ€.
μ₯μ
-
λΆμμ ν ν΄μ ν¨μλ₯Ό μ¬μ©νλ ν΄μν μ΄λΈκ³Ό λΉκ΅ν λ, μλ£μ μ κ·Όν λ μ΅μ μ κ²½μ° λ μ 리ν μκ°λ³΅μ‘λλ₯Ό κ°λλ€.
- mμ΄ νμν λ¬Έμμ΄μ κΈΈμ΄μΌ λ μκ°λ³΅μ‘λλ μ΄λ€.
- λ³΄ν΅ ν΄μν μ΄λΈμ νμ μκ°μ΄ μ΄κ³ ν΄μ ν¨μ νκ° μκ°μ΄ μ΄μ§λ§, λΆμμ ν ν΄μ ν μ΄λΈμ ν€ μΆ©λμ΄ μΌμ΄λ μ μμΌλ―λ‘, μ΄ λ μ μλ€.
- νΈλΌμ΄μμλ ν€ μΆ©λμ΄ μΌμ΄λμ§ μλλ€.
- μ¬λ¬ κ°μ΄ νλμ ν€μ μ°κ΄λμ΄ μμ§ μλ ν λ²ν·μ΄ νμ μλ€.
- ν΄μ ν¨μκ° μμ΄λ λλ€. ν€κ° λμ΄λ λ ν΄μ ν¨μλ₯Ό λ³κ²½ν νμλ μλ€.
- λͺ¨λ νλͺ©μ΄ ν€μ λ°λΌ μ¬μ μμΌλ‘ μ λ ¬λμ΄ μλ€.
λ¨μ
-
μ‘°νλ ν΄μ ν μ΄λΈλ³΄λ€ λ릴 μ μλ€.
- νΉν μ£Ό λ©λͺ¨λ¦¬μ λΉν΄ μμ μ κ·Ό λΉμ©μ΄ ν° νλ λμ€ν¬ λλΌμ΄λΈμ κ°μ 보쑰 κΈ°μ΅μ₯μΉμμ μ§μ μ½λλ€λ©΄ λμ± κ·Έλ λ€.
- λΆλμμμ κ³Ό κ°μ΄ λ¬Έμμ΄λ‘ μ₯ν©νκ² νμλλ μλ£μ κ²½μ° λ¬΄μλ―Ένκ² κΈΈκ² λμ΄μ§ μ λμ¬μ λ Έλλ₯Ό κ°μ§ μ μλ€.
-
νΈλΌμ΄κ° λ©λͺ¨λ¦¬λ₯Ό λ μλΉν μ μλ€.
- λλΆλΆμ ν΄μ ν μ΄λΈμμλ μ 체 νλͺ©μ νλμ λ©λͺ¨λ¦¬ μ²ν¬μ μ¬λ¦¬κ³€ νμ§λ§, νΈλΌμ΄μμλ κ²μ λ¬Έμμ΄μ κ° λ¬Έμλ§λ€ λ©λͺ¨λ¦¬κ° ν λΉλ μ μλ€.
πͺ ꡬν
νΈλ¦¬ ꡬ쑰μ κ° λ Έλμλ κ° λ¬Έμμ΄μ μΌλΆλ₯Ό ν¬ν¨νλ©°, μμ κ³Ό μ°κ²°λλ λ¬Έμμ΄μ μΌλΆλ₯Ό κ°μ§κ³ μμ΄μΌ νλ€λ μ μ λͺ μ¬!
μμ±μ/ν΄λμ€ μ μ
- λ£¨νΈ λ Έλλ μλ¬΄λ° λ¬Έμμ΄λ ν¬ν¨νμ§ μκ³ λͺ¨λ λ¬Έμμ΄μ μ λμ¬λ€μ μμ λ°°μ΄λ‘ κ°κ³ μμ΄μΌ νλ€.
Nodeν΄λμ€λ κ°Nodeμ μ 보λ₯Ό μ μν ν΄λμ€λ‘, μμ μ λ¬Έμ, μ°κ²°λλ λ¬Έμλ€μ μ 보λ₯Ό κ°κ³ μκ³ λ¬Έμμ΄μ΄ μμ±λλκ° μ¬λΆ λν μ μ₯νκ³ μλ€.
class Trie {
Node root;
static final int ALPHABET_SIZE = 26; // μνλ²³ κ°μ: 26
public Trie() {
this.root = new Node();
this.root.val = ' ';
}
public static class Node {
Node[] child = new Node[ALPHABET_SIZE]; // λ€λ‘ μ°κ²°λλ λ¬Έμμ΄μ indexννμ¬ μ μ₯νλ λ°°μ΄
boolean isTerminal = false; // νμ¬ λ
Έλκ° λ¬Έμμ΄μ λ§μ§λ§μΈμ§ μ¬λΆ
int childNum = 0; // νμ¬ λ
Έλμ μ°κ²°λ λ¬Έμμ΄ κ°μ
char val; // νμ¬ λ
Έλμ κ°
}
}
λ¬Έμμ΄ μ½μ (insert, charToInt)
charToInt()λ©μλλ κ° λ¬Έμμ΄μ 1κ° λ¨μ΄λ₯Όintν μ«μλ‘ λ³νν΄μ£Όλ λ©μλλ€.insert()λ©μλλ μ 체 λ¬Έμμ΄μ μͺΌκ°μ κ° λ Έλ(Node)μ μ μ₯νλ λ©μλλ€.
private int charToInt(char c) {
return c - 'a'; // μλ¬Έμλ§ μ·¨κΈνλ€λ κ°μ νμ `a`λ₯Ό λΊλ€.
}
public void insert(String str) {
int len = str.length();
Node cur = this.root;
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
int num = this.charToInt(c);
if (cur.child[num] == null) { // κΈ°μ‘΄μ nullμ΄λ©΄ μ°κ²° λ¬Έμμ΄λ‘ μ²μ μΆκ°λλ κ²
cur.child[num] = new Node();
cur.child[num].val = c;
cur.childNum++;
}
cur = cur.child[num];
}
cur.isTerminal = true;
}
μ°ΎκΈ°(find)
- λ¨μ΄λ₯Ό μ μ₯νμΌλ©΄ μ μ₯λμ΄ μλμ§ νμΈν μ μμ΄μΌ νλ€.
public boolean find(String str) {
int len = str.length();
Node cur = this.root;
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
int num = this.charToInt(c);
if (cur.child[num] == null) return false;
cur = cur.child[num];
}
return cur != null && cur.isTerminal;
}
μ 체 μ μ₯λ λ¬Έμμ΄ λ΄μ μΆλ ₯
- λͺ¨λ μ μ₯λ λ¨μ΄μ λ΄μμ μκΈ° μ½κ² μΆλ ₯ν μ μλλ‘ νλ λ©μλλ₯Ό ꡬνν΄λ³Ό μ μλ€.
private char intToChar(int i) {
return (char) (i + (int) 'a');
}
// μ¬μ©μκ° κ°νΈν νΈμΆλ§ νλ©΄ λλ ν¨μ
public void printTrie() {
this.printTrie(this.root, 0, new StringBuilder());
}
// λ΄λΆμμ μ¬κ·μ μΌλ‘ μννμ¬ λ
Έλμ μ μ₯λ κ°λ€ μΆμΆν΄ μΆλ ₯
private void printTrie(Node node, int idx, StringBuilder sb) {
Node cur = node;
Node[] child = cur.child;
StringBuilder builder = new StringBuilder(sb);
// λ£¨νΈ λ
Έλμλ μ μ₯λ κ²μ΄ μμΌλ―λ‘ κ·Έ μΈμ κ²½μ°μλ§ append
if (!cur.equals(this.root)) builder.append(intToChar(idx));
// μμ± λ
ΈλλΌλ©΄ μΆλ ₯
if (cur.isTerminal) System.out.println(builder);
// μ°κ²°λ λ
Έλλ€μ μννκΈ° μν΄ λ°λ³΅λ¬Έ μ¬μ©
for (int i = 0; i < ALPHABET_SIZE; i++) {
// nullμ΄λΌλ©΄ μ μ₯λ κ²μ΄ μμΌλ―λ‘ ν¨μ€
if (cur.child[i] == null) continue;
printTrie(child[i], i, builder);
}
}
μμ
- μμ λ μ¬κ·μ μΌλ‘ bottom-up λ°©μμΌλ‘ μ§νλκ³ , 3κ°μ§ κ²½μ°κ° μλ€.
-
μμ ν λ¬Έμκ° λ€λ₯Έ λ¬Έμμ μ λμ¬μΈ κ²½μ° -
isTerminalμfalseλ³κ²½DoλDoorμ μ λμ¬κ° λλ€. λ°λΌμ,Doλ₯Ό μμ νλ€λ©΄D,oμμoμisTerminalλ§falseλ‘ λ³κ²½νλ€.- λ¨μν μμ νλ©΄
Doorλν μ¬λΌμ§κ² λλ€.
- μμ ν λ¬Έμκ° κ³ μ νμ¬ λ€λ₯Έ λ¬Έμμ μ°κ΄μ΄ μλ κ²½μ° - κ΄λ ¨ λͺ¨λ λ Έλ μμ
-
μμ ν λ¬Έμμ μΌλΆκ° μ 체 μμ λ¬Έμμ μ λμ¬μΈ κ²½μ° - λ€λ₯Έ λ¬Έμμ μνκ°μ§ μλ κ³³κΉμ§λ§ μμ
Doorλ₯Ό μμ νλ €κ³ νλ€λ©΄Doκ° μκΈ°μ, μ 체 μμ λ₯Ό ν μ μκ³Doorμμ λ€μo,rλ§ μμ νλ€.
public void delete(String str) {
delete(this.root, str, 0);
}
private void delete(Node cur, String str, int idx) {
int len = str.length();
if ((cur.childNum == 0 && idx != len) || (idx == len && !cur.isTerminal)) {
throw new NoSuchElementException("Value" + str + " does not exist in Trie!");
}
if (idx == len) {
cur.isTerminal = false;
if (cur.childNum == 0) cur = null;
else {
char c = str.charAt(idx);
int num = charToInt(c);
delete(cur.child[num], str, idx + 1);
if (cur.child[num] == null) cur.childNum--;
if (cur.childNum == 0 && !cur.isTerminal) cur = null;
}
}
}
μ€μ λ‘λ
HashMapμ μ¬μ©ν΄ ꡬννλ κ²μ΄ λ ν¨μ¨μ μ΄λ€. μλλ μ΄λ₯Ό μ¬μ©ν ꡬνμ΄λ€.
ν΄λμ€ μμ±
TrieNodeλΒ μμλ Έλ λ§΅κ³ΌΒisLastCharλ₯Ό κ°μ§κ³ μλ€.isLastCharλ 'DEV'λΌλ λ¨μ΄μμ [D], [E]λ λ§μ§λ§ κΈμκ° μλμ§λ§ [V]λ λ§μ§λ§ κΈμλ‘, ν λ¨μ΄κ° μμ±λλ μμ μμ μ μ μλλ‘ νλ κ°μ΄λ€.
public class TrieNode {
private Map<Character, TrieNode> childNodes = new HashMap<>();
// λ§μ§λ§ κΈμ μ¬λΆ
private boolean isLastChar;
// μμ λ
Έλ λ§΅ Getter
Map<Character, TrieNode> getChildNodes() {
return this.childNodes;
}
// λ§μ§λ§ κΈμμΈμ§ μ¬λΆ Getter
boolean isLastChar() {
return this.isLastChar;
}
// λ§μ§λ§ κΈμμΈμ§ μ¬λΆ Setter
void setIsLastChar(boolean isLastChar) {
this.isLastChar = isLastChar;
}
}
- Trieλ κΈ°λ³Έμ μΌλ‘Β λΉ λ¬Έμμ΄μ κ°μ§λ λ£¨νΈ λ Έλλ§ κ°μ§κ³ μλ€.
- μ΄ νμ λμ¬
insert()λ₯Ό ν΅ν΄ λ¨μ΄λ₯Ό λ£μ΄ κ·Έμ λ§κ² μμ λ Έλκ° μμ±λλ€.
public class Trie {
private TrieNode rootNode;
public Trie() {
rootNode = new TrieNode();
}
}
insert
-
μ λ ₯λ°μ λ¨μ΄μ κ° μνλ²³μ κ³μΈ΅κ΅¬μ‘°μ μμ λ Έλλ‘ λ§λ€μ΄ λ£λλ€.
- μ΄λ―Έ κ°μ μνλ²³μ΄ μ‘΄μ¬νλ©΄ κ³΅ν΅ μ λμ΄κΉμ§λ μμ±νμ§ μλλ€.
- μ¦, ν΄λΉ κ³μΈ΅ λ¬Έμμ μμ λ Έλκ° μ‘΄μ¬νμ§ μμ λλ§ μμ λ Έλλ₯Ό μμ±ν΄μ€λ€.
- μ΄ν λ§μ§λ§ κΈμμλ "μ¬κΈ°κΉμ§λ₯Ό λμΌλ‘ νλ λ¨μ΄κ° μ‘΄μ¬νλ€"λ νμλ₯Ό μν΄
isLastCharλ₯Όtrueλ‘ ν΄μ€λ€.
void insert(String word) {
TrieNode thisNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
thisNode = thisNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
}
thisNode.setIsLastChar(true);
}
contains
-
νΉμ λ¨μ΄κ° Trieμ μ‘΄μ¬νλμ§λ₯Ό νμΈνκΈ° μν΄μλ μλ 2κ°μ§ 쑰건μ λ§μ‘±ν΄μΌ νλ€.
- λ£¨νΈ λ ΈλλΆν° μμλλ‘ μνλ²³μ΄ μΌμΉνλ μμ λ Έλλ€μ΄ μ‘΄μ¬ν κ²
- ν΄λΉ λ¨μ΄μ λ§μ§λ§ κΈμμ ν΄λΉνλ λ
Έλμ
isLastCharκ°trueμΌ κ²
boolean contains(String word) {
TrieNode thisNode = this.rootNode;
for (int i = 0; i < word.length(); i++) {
char character = word.charAt(i);
TrieNode node = thisNode.getChildNodes().get(character);
if (node == null) return false;
thisNode = node;
}
return thisNode.isLastChar();
}
delete
- Trieμ λ£μλ λ¨μ΄λ₯Ό μμ νλ κ³Όμ μ΄λ€.
contains()μ²λΌ μ£Όμ΄μ§ λ¨μ΄λ₯Ό μ°Ύμ νμ λ Έλλ‘ λ¨μ΄ κΈΈμ΄λ§νΌ λ΄λ €κ°λ€.- λ¨, λ Έλλ€μ΄ λΆλͺ¨ λ Έλμ μ 보λ₯Ό κ°μ§κ³ μμ§ μκΈ°μ, νμ λ Έλλ‘ λ΄λ €κ°λ©° μμ λμ λ¨μ΄λ₯Ό νμνκ³ λ€μ μ¬λΌμ€λ©΄μ μμ νλ κ³Όμ μ΄ μ½λ°±νμμΌλ‘ ꡬνλμ΄μΌ νλ€λ κ²μ΄λ€.
κ·Έλ¦¬κ³ μλμ μμ 쑰건λ€μ νμΈν΄μΌ νλ€.
- μμ λ Έλλ₯Ό κ°μ§κ³ μμ§ μμμΌ νλ€.
- μμ λ₯Ό μμνλ 첫 λ
Έλλ
isLastChar == trueμ¬μΌ νλ€. - μμ λ₯Ό μ§ννλ μ€μλ
isLastChar == falseμ¬μΌ νλ€.
void delete(String word) {
delete(this.rootNode, word, 0);
}
private void delete(TrieNode thisNode, String word, int index) {
char character = word.charAt(index);
// Trieμ μλ λ¨μ΄μΈ κ²½μ° μλ¬ μΆλ ₯
if(!thisNode.getChildNodes().containsKey(character))
throw new Error("There is no [" + word + "] in this Trie.");
TrieNode childNode = thisNode.getChildNodes().get(character);
index++;
// λ¨μ΄μ κΈΈμ΄λ§νΌ νμ λ
Έλλ‘ μ¬κ·
if(index == word.length()) {
// μμ 쑰건 2λ² νλͺ©
// POμ κ°μ΄ λ
Έλλ μ‘΄μ¬νμ§λ§ insertν λ¨μ΄κ° μλ κ²½μ° μλ¬ μΆλ ₯
if (!childNode.isLastChar())
throw new Error("There is no [" + word + "] in this Trie.");
childNode.setIsLastChar(false);
// μμ 쑰건 1λ² νλͺ©
// μμ λμ λ¨μ΄μ μ μΌ λμΌλ‘μ¨ μμ λ
Έλκ° μμΌλ©΄(μ΄ λ¨μ΄λ₯Ό ν¬ν¨νλ λ κΈ΄ λ¨μ΄κ° μμΌλ©΄) μμ μμ
if (childNode.getChildNodes().isEmpty())
thisNode.getChildNodes().remove(character);
} else {
delete(childNode, word, index); // μ½λ°±ν¨μλΆλΆ
// μμ 쑰건 1,3λ² νλͺ©
// μμ μ€, μμ λ
Έλκ° μκ³ νμ¬ λ
Έλλ‘ λλλ λ€λ₯Έ λ¨μ΄κ° μλ κ²½μ° μ΄ λ
Έλ μμ
if(!childNode.isLastChar() && childNode.getChildNodes().isEmpty())
thisNode.getChildNodes().remove(character);
}
}